# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 19_new_middle_number_R.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/2/8 15:35
------------------------------------------
    给定两个升序数组，如何找出这两个数组归并以后新的升序数组的中位数
    demo1:
        list_a = [1, 3, 5, 6, 7, 10]
        list_b = [2, 4, 9, 11]
        list_ab = [1, 2, 3, 4, 5, 5, 6, 7, 9, 10, 11]
        中位数为 5

    demo2:
        list_a = [3, 5, 7, 8, 9]
        list_b = [1, 2, 6, 7, 15]
        list_ab = [1, 2, 3, 5, 6, 7, 7, 8, 9, 15]
        中位数为 (6 + 7) / 2 = 6.5
"""


def find_median_sorted_arrays(array_a, array_b):
    len_a, len_b = len(array_a), len(array_b)

    # 如果数据组 a的长度大于数组 b的长度，则交换数组
    if len_a > len_b:
        array_a, array_b = array_b, array_a
        len_b, len_a = len_a, len_a

    if len_b == 0:
        raise ValueError("有数组的长度为0")

    # 这个"//"总是弄混：除完后向小取整
    start, end, half_len = 0, len_a, (len_a + len_b + 1) // 2

    while start <= end:
        i = (start + end) // 2
        j = half_len - i

        if i < len_a and array_b[j - 1] > array_a[i]:
            # i 偏小了，需要右移
            start = i + 1

        elif i > 0 and array_a[i - 1] > array_b[j]:
            # i偏大了，需要左移
            end = i - 1

        else:
            # i刚好合适，或i已达到数组边界
            if i == 0:
                max_of_left = array_b[j - 1]

            elif j == 0:
                max_of_left = array_a[i - 1]

            else:
                max_of_left = max(array_a[i - 1], array_b[j - 1])

            if (len_a + len_b) % 2 == 1:
                # 如果大数组的长度是奇数，中位数就是左半部分的最大值
                return max_of_left

            if i == len_a:
                min_of_right = array_b[j]

            elif j == len_b:
                min_of_right = array_a[i]

            else:
                min_of_right = min(array_a[i], array_b[j])

            # 如果大数组的长度是偶数，取左侧最大值和右侧最小值的平均值
            return (max_of_left + min_of_right) / 2.0


def demo():
    my_array_a = [3, 5, 6, 7, 8, 12, 20]
    my_array_b = [1, 10, 17, 18]
    print(find_median_sorted_arrays(my_array_a, my_array_b))


if __name__ == '__main__':
    demo()
